package binarySearch;

public class D230717 {

    // 一、数组中的逆序对
    int cnt = 0;
    public int InversePairs(int[] array) {
        if (array.length != 0) {
            divide(array, 0, array.length - 1);
        }
        return cnt;
    }
    // 划分
    public void divide(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        // 递归
        divide(array, start, mid);
        divide(array, mid + 1, end);
        // 合并
        merge(array, start, mid, end);
    }
    // 合并两个有序数组
    public void merge(int[] array, int start, int mid, int end) {
        //临时数组
        int[] tmp = new int[end - start + 1];

        // i 和 j 分别表示两个数组的下标
        // k 表示临时数组的下标
        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) {
            // 两个数组中, 取较小的放到临时数组中
            if (array[i] <= array[j]) {
                tmp[k++] = array[i++];
            }
            else {
                tmp[k++] = array[j++];
                // 后面的数组中元素较小，那么逆序对数量 + mid - i + 1
                // 因为两个数组已经有序了，如果 array[j] < array[i]
                // 那么 array 中 [i ~ mid]，都大于 array[j]
                cnt = (cnt + mid - i + 1) % 1000000007;
            }
        }
        //未遍历完的直接放在右侧
        while (i <= mid) {
            tmp[k++] = array[i++];
        }
        while (j <= end) {
            tmp[k++] = array[j++];
        }
        //将临时数组的值覆盖原来数组
        for (k = 0; k < tmp.length; k++) {
            array[start + k] = tmp[k];
        }
    }

    // 二、旋转数组的最小数字
    // [1,2,3,4,4,5,5]
    // [4,5,5,1,2,3,4]
    // 可以将这个旋转数组 分为两部分
    // 前半部分是非降序的, 后半部分也是非降序的，非降序不是升序，是 <=
    // 而且前半部分都 大于等于 后半部分
    // 那么使用二分查找，找两个部分的分界处，分界处较小的就是最小值
    public int minNumberInRotateArray(int [] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int left = 0;
        int right = array.length - 1;
        int mid = 0;

        while (array[left] >= array[right]) {
            if (left == right - 1) {
                // left 和 right 相邻
                // 查找结束
                // 返回较小的right
                mid = right;
                break;
            }
            mid = (left + right) >> 1;  // 取中

            if (array[mid] > array[right]) {
                // mid 大于 right
                // 说明当前 mid 在前半部分, 最小值在 mid 右边
                left = mid;
            } else if (array[mid] < array[right]){
                // mid 小于 right
                // 说明当前 mid 在后半部分, 最小值在 mid 左边
                right = mid;
            } else {
                // mid 等于 right
                // 不能确定 mid 在哪边
                right--;
            }
        }
        return array[mid];
    }


    // 比较版本号
    public int compare (String version1, String version2) {
        int length1 = version1.length();
        int length2 = version2.length();
        int i = 0;
        int j = 0;
        while (i < length1 || j < length2) {
            long num1 = 0;
            while (i < length1 && version1.charAt(i) != '.') {
                num1 = num1 * 10 + version1.charAt(i++) - '0';
            }
            i++; // 跳过 '.'
            long num2 = 0;
            while (j < length2 && version2.charAt(j) != '.') {
                num2 = num2 * 10 + version2.charAt(j++) - '0';
            }
            j++; // 跳过 '.'
            if (num1 > num2) {
                return 1;
            }
            if (num1 < num2) {
                return -1;
            }
        }
        return 0;
    }
}
